Pada 107 BC, Sulla dilantik sebagai quaestor pada Gaius Marius, yang telah dilantik sebagai konsol Rom bagi tahun itu. Marius kemudian telah mengambil alih kepimpinan tentera Rom dalam perang bagi menentang Raja Jugurtha dari Numidia di Utara Afrika.

Perang Jugurthine telah bermula pada 112 BC, tetapi legion Rom di bawah Quintus Caecilius Metellus telah gagal mematahkannya. Gaius Marius, leftenan di bawah Metellus, meihat peluang untuk mengatasi komandernya dan menyuap khabar angin mengenai ketidakcekapannya dan kelewatan bagi publicani (pengumpulan cukai) di regin tersebut. Usaha ini menyebabkan usul penyingkiran Metellus; disebalik taktik melewat-lewatkan oleh Metellus, Marius kembali ke Rom untuk bertanding bagi jawatan konsol lalu mengambil alih kempen tersebut.

Di bawah pimpinan Marius, pasukan Rom menurut rancangan yang sama seperti di bawah Metellus dan akhirnya berjaya menewaskan pihak Numidian pada tahun 106 BC, sebahagian besarnya berdasarkan inisiatif Sulla bagi menawan raja Numidian. Dia kemudiannya memujuk Raja Bocchus I dari Mauretania, kerajaan berhampiran, untuk mengkhianati Jugurtha, yang telah melarikan diri ke Mauretania untuk perlindungan. Ia merupakan operasi merbahaya dari mula, dengan Raja Bocchus menimbangkan kelebihan menyerahkan Jugurtha pada Sulla atau menyerahkan Sulla pada Jugurtha.[6] Publisiti yang didapati hasil kejayaan ini meningkatkan kerjaya politik Sulla. Lebih mengganggu Marius, patung Sulla berkuda yang bersepuh didermakan oleh Raja Bocchus dan didirikan di Forum bagi meraikan pencapaiannya.